package Interview.Amazon;

import java.util.List;

import org.apache.commons.collections.CollectionUtils;

import com.google.common.collect.Lists;

/**
 * @author leiwenkang <leiwenkang@kuaishou.com>
 * Created on 2022-08-07
 */
public class Test08找出数组中和为某值的所有组合 {
    public static void main(String[] args) {
        int[] array = {10, 3, 5, 2, 6, 4, 0};
        List<List<Integer>> result = findTarget(array, 10);
        System.out.println(result);
    }

    private static List<List<Integer>> findTarget(int[] array, int target) {
        if (array == null || array.length == 0) {
            return null;
        }
        List<List<Integer>> result = Lists.newArrayList();
        for (int i = 0; i < array.length; i++) {
            List<List<Integer>> list = findTarget(array, i, target);
            if (CollectionUtils.isNotEmpty(list)) {
                result.addAll(list);
            }
        }
        return result;
    }

    private static List<List<Integer>> findTarget(int[] array, int index, int target) {
        if (index == array.length) {
            return null;
        }
        List<List<Integer>> result = Lists.newArrayList();
        if (target == array[index]) {
            result.add(Lists.newArrayList(target));
        }

        for (int i = index; i < array.length; i++) {
            List<List<Integer>> tempList = findTarget(array, i + 1, target - array[index]);
            if (CollectionUtils.isNotEmpty(tempList)) {
                for (List<Integer> list : tempList) {
                    list.add(array[index]);
                }
                result.addAll(tempList);
            }
        }
        return result;
    }

}
